package com.hh.TreeQuestions;

/**
 * @Author hanghao
 * @Date 2023/7/18 16:28
 * @Version 1.0
 * 不同的二叉搜索树
 * middle
 */

public class No96 {
    public int numTrees(int n) {
        //dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。
        //递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}
